def make_mat(m, n):
    mat = []
    for i in range(m):
        mat.append([None] * n)
    return mat


def print_lcs(x, c, i, j):
    if i == 0 or j == 0:
        return
    if c[i][j] == 0:
        return
    else:
        print_lcs(x, c, i - 1, j - 1)
        print(x[i - 1], end="")


def lcs(x, y):
    m = len(x)
    n = len(y)
    c = make_mat(m+1, n+1)
    max_len = 0
    max_i = -1
    max_j = -1
    for i in range(0, m+1):
        c[i][0] = 0
    for i in range(1, n+1):
        c[0][i] = 0

    for i in range(1, m+1):
        for j in range(1, n+1):
            if x[i-1] == y[j-1]:
                c[i][j] = c[i-1][j-1] + 1
            else:
                c[i][j] = 0
            if c[i][j] > max_len:
                max_len = c[i][j]
                max_i = i
                max_j = j

    print_lcs(x, c, max_i, max_j)


if __name__ == '__main__':
    x = "xzyzzyx"
    y = "zxyyzxz"
    lcs(x, y)
    print("")

    x = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCALLAAQANKESSSESFISRLLAIVAD"
    y = "MAEEEVAKLEKHLMLLRQEYVKLQKKLAETEKRCTLLAAQANKENSNESFISRLLAIVAG"
    lcs(x, y)
